package com.guet.DataStructures.linkedlist;

import java.util.Stack;

/**
 * @author MicahYin
 * @date 2020/10/13 16:50
 * java数据结构————链表
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode node1 = new HeroNode(1,"姜子牙","姜太公");
        HeroNode node2 = new HeroNode(2,"哪吒","三太子");
        HeroNode node3 = new HeroNode(3,"雷震子","鸟人");
        SingleLinkList singleLinkList = new SingleLinkList();
        singleLinkList.addByOrder(node3);
        singleLinkList.addByOrder(node1);
        singleLinkList.addByOrder(node2);



        HeroNode node4 = new HeroNode(4,"刘备","刘玄德");
        HeroNode node5 = new HeroNode(5,"关羽","关云长");
        HeroNode node6 = new HeroNode(6,"张飞","张翼德");
        SingleLinkList singleLinkList2 = new SingleLinkList();
        singleLinkList2.addByOrder(node4);
        singleLinkList2.addByOrder(node5);
        singleLinkList2.addByOrder(node6);



        singleLinkList.list();
        System.out.println("-----------合并之后---------");
        //将两个顺序链表合并
        SingleLinkList linkList = merge2LinkList(singleLinkList.getHead(),singleLinkList2.getHead());
        linkList.list();

    }
    /**
     * java链表面试题求解
     * 1.获取链表有效节点的个数
     */
    /**
     * @param head  链表的头节点
     * @return 链表的有效节点个数
     */
    public static int getLength(HeroNode head){
        int length = 0;
        while (head.next!=null){
            length++;
            head = head.next;
        }
        return length;
    }
    /**
     * 2.查找单链表中的倒数第k个节点[新浪面试题]
     * 思路：
     *    ①编写一个方法，接收head节点，同时接收一个index、
     *    ②index表示是倒数第index个节点
     *    ③先把链表从头到尾遍历，得到链表的总长度getLength
     *    ④得到size后，我们从链表的第一个开始遍历(size-index)个，即可得到所求
     *    ⑤如果找到该节点，则返回，否则返回null
     */
    public static HeroNode findLastK(HeroNode head,int index){
        //判断链表是否为空，否则返回null
        if (head.next==null){
            return null;
        }
        int length = getLength(head);
        if (index<=0||index>length){
            return null;
        }
        for (int i=length-index;i>=0;i--){
            head = head.next;
        }
        return head;
    }
    /**
     * 3.腾讯面试题
     * 将单链表反转（***头插法***）
     * 思路：
     *    ①新建一个新的链表
     *    ②遍历原始链表，将遍历到的节点按头插法加入到新的链表中
     */
    public static void reverseList(HeroNode head){
        //如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if (head.next==null||head.next.next==null){
            return;
        }
        HeroNode cur = head.next;
        HeroNode next = null;//指向当前节点[cur]的下一个节点
        HeroNode reverseHead = new HeroNode(0,"","");
        while (cur!=null){
            next=cur.next;
            cur.next=reverseHead.next;
            reverseHead.next = cur;
            cur=next;
        }
        head.next=reverseHead.next;
    }

    /**
     * 面试题：从尾到头打印单链表
     * 思路：①利用栈数据结构，将各个节点的数据压入到栈中....随后利用栈先进先出的特性，可以实现目标
     *      ②先将链表进行反转操作，随后再遍历链表------不建议，破坏了原来的数据结构
     */
    //此处代码使用思路①
    public static void reversePrint(HeroNode head){
        if (head.next==null){
            System.out.println("空链表，不能打印...");
            return;
        }
        Stack<HeroNode> stack =new Stack<>();
        //定义一个临时变量保存头结点
        HeroNode temp=head;
        while (temp.next!=null){
            stack.add(temp.next);
            temp=temp.next;
        }
        while (!stack.isEmpty()){
            System.out.println(stack.pop());
        }
    }
    /**
     * 面试题：合并两个有序的单链表
     * 思路：
     *      ①先创建一个新的链表，作为最后存储结果的链表
     *      ②分别从两个有序链表从选取一个较小的数插入的新的单链表中
     *      ③知道两个有序的单链表中的数据全部加入到新的单链表中为止
     */
    /**
     * 合并两个有序的单链表
     * @param head1 链表1的头
     * @param head2 链表2的头
     * @return 合并之后的有序链表
     */
    public static SingleLinkList merge2LinkList(HeroNode head1,HeroNode head2){
        SingleLinkList singleLinkList = new SingleLinkList();
        //定义一个结束标志
        boolean flag=true;
        while (flag){
            //若head1为null，则直接将head2所有的节点加入到singleLinkList即可
            if (head1.next==null){
                while (head2.next!=null){
                    //此处因为add方法的特殊性，所以需要new一个新的节点，再将其存入singleLinkList
                    singleLinkList.add(new HeroNode(
                            head2.next.no,head2.next.name,head2.next.nickname));
                    head2=head2.next;
                }
                return singleLinkList;
            }
            //同理，若head2为null
            if (head2.next==null){
                while (head1.next!=null){
                    singleLinkList.add(new HeroNode(
                            head1.next.no,head1.next.name,head1.next.nickname));
                    head1=head1.next;
                }
                return singleLinkList;
            }
            if (head1.next.no>=head2.next.no){
                singleLinkList.add(new HeroNode(
                        head2.next.no,head2.next.name,head2.next.nickname));
                head2=head2.next;
            }else {
                singleLinkList.add(new HeroNode(
                        head1.next.no,head1.next.name,head1.next.nickname));
                head1=head1.next;
            }
            if (head1.next==null&&head2.next==null){
                flag=false;
            }
        }
        return singleLinkList;
    }
}
//定义SingleLinkedList管理我们的英雄
class SingleLinkList{
    //初始化头结点----头结点很关键，不要动，不存放具体的数据
    private HeroNode head = new HeroNode(0,"","");
    /**
     * 添加节点到单向链表
     * 1. 找到当前链表的最后节点
     * 2. 将最后这个节点的next指向新的节点
     */
    public void add(HeroNode heroNode){
        //因为head节点不能动，因此我们需要一个辅助遍历temp
        HeroNode temp = head;
        //遍历链表，找到最后的节点
        while (temp.next!=null){
            temp = temp.next;
        }
        //当while循环结束时，temp就指向了链表的最后
        temp.next = heroNode;
    }
    /**
     * 按顺序将节点添加到链表
     * 1.先按顺序遍历链表，如找到应当的位置则将新节点插入，如未找到则打印提示
     * @param heroNode
     */
    public void addByOrder(HeroNode heroNode){
        HeroNode temp = head;
        boolean flag=false;//是否已存在该编号
        while (true){
            if (temp.next==null){
                break;
            }else if (temp.next.no>heroNode.no){
                //找到新节点应该插入的位置
                break;
            }else if (temp.next.no==heroNode.no){
                flag=true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            System.out.printf("当前编号%d已存在...",heroNode.no);
        }else {
            //插入数据
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    /**
     * 遍历显示链表中的元素
     */
    public void list(){
        if (head.next==null){
            System.out.println("链表为空");
            return;
        }
        //头结点不能动，因此需要一个辅助变量来遍历
        HeroNode temp=head;
        while (temp.next!=null){
            temp = temp.next;
            System.out.println(temp);
        }
    }

    /**
     * 修改节点的信息，根据no编号来修改，所以no编号不能修改
     * @param heroNode
     */
    public void update(HeroNode heroNode){
        //判断是否为空
        if (head.next==null){
            System.out.println("链表为null....");
            return;
        }
        //不为空，则遍历找到需要修改的节点
        HeroNode temp = head;
        //是否找到修改的节点
        boolean flag = true;
        while (true){
            if (temp.next==null){
                flag=false;
                break;
            }else if (temp.next.no==heroNode.no){
                //找到该节点的前一个节点，跳出
                break;
            }
            temp = temp.next;
        }
        //找到该节点的前一个节点
        if (flag){
            temp.next.nickname = heroNode.nickname;
            temp.next.name = heroNode.name;
        }else {
            System.out.printf("未找到编号为%d的节点...",heroNode.no);
        }
    }

    /**
     * 删除节点
     * 思路：
     * 1.head不能动。需要辅助节点temp，找到待删除节点的前一个节点
     * 2.temp.next = temp.next.next
     * @param no
     */
    public void del(int no){
        HeroNode temp = head;
        //是否找到该节点
        boolean flag = true;
        while (true){
            if (temp.next==null){
                flag=false;
                break;
            }else if (temp.next.no==no){
                //找到该节点的前一个节点，跳出
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.next = temp.next.next;
        }else {
            System.out.printf("未找到%d节点",no);
        }
    }

    public HeroNode getHead() {
        return head;
    }
}
/**
 * 定义HeroNode,每个HeroNode对象就是一个节点
 */
class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;
    //构造函数
    public HeroNode(int no,String name,String nickname){
        this.no=no;
        this.name=name;
        this.nickname=nickname;
    }
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}
